package model;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;
/**
 * @author Darko Martinovikj
 * @version 1.2 01.03.2013
 * 
 * Class representing a graph without variables
 *  */

/**
 * Class representing a graph without variables
 * @author DarkoLaptop
 *
 */
public class TransitionSystem {
	protected int nodesCount;
	protected NodeTransitionSystem adjList[];
	protected int startNodeIndex;
	protected TransitionHashTable transitionTable;
	protected int maxNodeIndex;
	/**
	 * This method is the constructor of the class.
	 * 
	 * @param int maxNumberNodes- the maximal number of nodes in the graph
	 */
	public TransitionSystem(int maxNumberNodes) {
		this.nodesCount = 0;
		adjList = new NodeTransitionSystem[maxNumberNodes];
		startNodeIndex=-1;
		transitionTable = new TransitionHashTable();
		maxNodeIndex=-1;
	}
	
	/**
	 * This method is the constructor of the class. Creates a new empty graph with maximal number of 10000 nodes
	 * 
	 */
	public TransitionSystem() {
		this.nodesCount = 0;
		adjList = new NodeTransitionSystem[10000];
		startNodeIndex=-1;
		transitionTable = new TransitionHashTable();
		maxNodeIndex=-1;
	}
	
	/**
	 * Method for adding a Node to the graph. The node index and name must be specified. The node by default is not bad. 
	 * 
	 * @param int index- the index of the node
	 * @param String name - the name of the node
	 */
	public void addNode(int index,String name){
		adjList[index]=new NodeTransitionSystem(index, name);
		nodesCount++;
		if(index>maxNodeIndex)
			maxNodeIndex=index;
	}
	
	/**
	 * Method for adding a Node to the graph. The node index and name must be specified. Also is the node bad must be specified. 
	 * 
	 * @param int index - the index of the node
	 * @param String name - the name of the node
	 * @param boolean isBadState - is the node bad
	 */
	public void addNode(int index,String name,boolean isBadNode){
		adjList[index]=new NodeTransitionSystem(index, name, isBadNode);
		nodesCount++;
		if(index>maxNodeIndex)
			maxNodeIndex=index;
	}
	
	/**
	 * Method for adding a edge in the graph. The indexes of the two nodes must be specified and also the transition name
	 * Also the transition is added in the transition hash table as controllable transition
	 * 
	 * @param int indexFrom - the index of the from node
	 * @param String transitionName - the name of the transition
	 * @param int indexTo - the index of the to node
	 */
	public void addEdge(int indexFrom,String transitionName,int indexTo){
		adjList[indexFrom].addNeighbor(adjList[indexTo], transitionName);
		transitionTable.insertTransition(transitionName, true);
	}

	/**
	 * Method for setting the initial node to be the specified node with given index.
	 * 
	 * @param int index - the index of node we want to be initial
	 */
	public void setInitialNode(int index){
		startNodeIndex=index;
	}
	
	
	/**
	 * Method for getting the initial node if exists. If that node doesn't exist than a null is returned
	 * 
	 * @return NodeTransitionSystem - the initial node or null
	 */
	public NodeTransitionSystem getInitialNode(){
		if (startNodeIndex==-1)
			return null;
		else
			return adjList[startNodeIndex];
	}	
	
	/**
	 * Method for setting a node with given index to be a bad node
	 * 
	 * @param int index - the index of the node we want to be bad
	 */	
	public void setBadNode(int index){
		adjList[index].setBadNode(true);
	}
	
	/**
	 * Method for getting all of the neighbours of a node with given index
	 * 
	 * @param int index - the node index 
	 * @return LinkedList<EdgeTransitionSystem> - the list of all of the neighbours of the given node
	 */
	public LinkedList<EdgeTransitionSystem> getNodeNeighbors(int index){
		return adjList[index].getNeighbors();
	}
	
	/**
	 * Method for getting all of the parents of a node with given index
	 * 
	 * @param int index - the node index 
	 * @return LinkedList<EdgeTransitionSystem> - the list of all of the parents of the given node
	 */
	public LinkedList<EdgeTransitionSystem> getNodeParents(int index){
		return adjList[index].getParents();
	}
	
	/**
	 * This method is used for printing graph information without transition information
	 *
	 * @return String - the graph information
	 */
	@Override
	public String toString() {
		String ret = new String();
		for (int i = 0; i < this.nodesCount; i++)
			if(adjList[i]!=null)
				ret += adjList[i] + "\n";
		return ret;
	}
	
	/**
	 * This method is used for printing graph information with transition information
	 *
	 * @return String - the graph information
	 */
	public String toStringTransitionPrint() {
		System.out.println(nodesCount);
		String ret = new String();
		for (int i = 0; i <= this.maxNodeIndex; i++)
			if(adjList[i]!=null)
				ret += adjList[i].toStringWithNeightbours() + adjList[i].toStringParents() + "\n";
		return ret;
	}
	
	/**
	 * Method for returning all of the transitions in the graph
	 *
	 *@return String[] - Arrays of string, representing transitions name
	 */
	public String[] getAllTransitions() {
		return transitionTable.getAllTransitions();
	}
	
	/**
	 * Method for returning all of the transitions which are controllable as Array of string
	 *
	 *@return String[] - Arrays of string, representing transitions name
	 */
	public String[] getAllControllableTransitions() {
		return transitionTable.getAllControllableTransitions();
	}
	
	/**
	 * Method for returning all of the transitions which are uncontrollable as Array of string
	 *
	 *@return String[] - Arrays of string, representing transitions name
	 */
	public String[] getAllUncontrollableTransitions() {
		return transitionTable.getAllUncontrollableTransitions();
	}
	
	/**
	 * Method for setting the type of the transition. If a transition with that name doens't exist 
	 * method does nothing
	 *
	 *@param String transitionName - The name of the transition
	 *@param boolean isControllable - Is the transition Controllable
	 *
	 */
	public void setTransitionType(String transitionName,boolean isControllable){
		if(transitionTable.isControllableTransition(transitionName)!=null)
			transitionTable.insertTransition(transitionName, isControllable);
	}
	
	/**
	 * Method for returning if a given transition is Controllable. If that transition doesn't exist returns null
	 *
	 *@return Boolean - if the transition is Controllable, or null if that transition doesn't exist
	 */
	public Boolean isControllableTransition(String transitionName){
		return transitionTable.isControllableTransition(transitionName);
	}
	
	/** Method for removing the edge from the graph. The appropriate neighbour and parent links are removed 
	 * 
	 * @param EdgeTransitionSystem transition - The transition Edge
	 */
	public void removeTransition(EdgeTransitionSystem transition){
		adjList[transition.getFromNode().getIndex()].removeNeighbour(transition);
		adjList[transition.getToNode().getIndex()].removeParent(transition);
	}
	
	/**
	 * Method for removing a node from the graph. All the transitions (edges) are remove before removing the node 
	 * @param int index - the index of the node
	 */
	public void removeNode(int index){
		LinkedList<EdgeTransitionSystem> list=new LinkedList<EdgeTransitionSystem>();
		for(EdgeTransitionSystem edge:adjList[index].getNeighbors()){
			list.add(edge);
		}
		for(EdgeTransitionSystem edge:list)
			this.removeTransition(edge);
		list=new LinkedList<EdgeTransitionSystem>();
		for(EdgeTransitionSystem edge:adjList[index].getParents()){
			list.add(edge);
		}
		for(EdgeTransitionSystem edge:list)
			this.removeTransition(edge);
		adjList[index]=null;
	}
	
	
	/**
	 * Method for getting all the nodes with the same transition trace counting from the startNode
	 * @param LinkedList<String> transitionsNameTrace - the trace of the transitions'  Name
	 * @return LinkedList<NodeTransitionSystem> - list of the nodes with the same transition trace
	 */
	public LinkedList<NodeTransitionSystem> getAllNodesWithSameTraces(LinkedList<String> transitionsNameTrace){
		LinkedList<NodeTransitionSystem> currentNodeQueue=new LinkedList<NodeTransitionSystem>();
		currentNodeQueue.addLast(adjList[startNodeIndex]);
		for(String currentTransitionName:transitionsNameTrace){
			LinkedList<NodeTransitionSystem> nextNodeQueue=new LinkedList<NodeTransitionSystem>();
			while (!currentNodeQueue.isEmpty()) {
					LinkedList<EdgeTransitionSystem> neighbours=currentNodeQueue.removeFirst().getNeighbors();
					for(EdgeTransitionSystem neighbour:neighbours)
						if(neighbour.getTransitionName().equals(currentTransitionName)){
							if(!nextNodeQueue.contains(neighbour.getToNode()))
								nextNodeQueue.addLast(neighbour.getToNode());
						}
			}
			currentNodeQueue=nextNodeQueue;
		}
		return currentNodeQueue;
	}
	
	/** Method for getting all the nodes which end with a given transition trace
	 * @param transitionTrace - the trace of transition
	 * @return list of nodes
	 */
	public LinkedList<NodeTransitionSystem> getAllNodesWithSameTrace(String transitionTrace){
		String[] transitionList=transitionTrace.split(" ");
		LinkedList<String> transitionTraceList=new LinkedList<String>();
		for(String element:transitionList)
			transitionTraceList.addLast(element);
		return getAllNodesWithSameTraces(transitionTraceList);
	}
	
	/** Method for getting all the bad nodes in the graph
	 * @return list of bad nodes
	 */
	public LinkedList<NodeTransitionSystem> getAllBadNodes(){
		LinkedList<NodeTransitionSystem> lista=new LinkedList<NodeTransitionSystem>();
		for(int i=0;i<nodesCount;i++)
			if(adjList[i].isBadNode())
				lista.add(adjList[i]);
		return lista;
		
	}
	
	/** Method for checking if a node with the given index exists in the graph
	 * @param index - the index of the node
	 * @return - true/false
	 */
	public boolean isSetNode(int index){
		return adjList[index]!=null;
	}
	
	/** Method for getting the max depth of the graph starting from the start node
	 * @return - int the max depth of the graph
	 */
	public int getMaxDepth(){
		int depth[]=new int[maxNodeIndex+1];
		Arrays.fill(depth, Integer.MAX_VALUE);
		depth[startNodeIndex]=0;
		LinkedList<NodeTransitionSystem> queue=new LinkedList<NodeTransitionSystem>();
		queue.addLast(adjList[startNodeIndex]);
		int maxDepth=0;
		while(!queue.isEmpty()){
			NodeTransitionSystem currentNode=queue.removeFirst();
			for(EdgeTransitionSystem transition:currentNode.getNeighbors()){
				if(depth[transition.getFromNode().getIndex()]+1<depth[transition.getToNode().getIndex()]){
					depth[transition.getToNode().getIndex()]=depth[transition.getFromNode().getIndex()]+1;
					if(depth[transition.getFromNode().getIndex()]+1>maxDepth)
						maxDepth=depth[transition.getFromNode().getIndex()]+1;
					queue.addLast(transition.getToNode());
				}
			}
		}
		return maxDepth;
	}
	
	/** Method for generating all the possible paths in the graph with the max length - the max depth of the graph
	 * @return list of the traces (paths)
	 */
	public LinkedList<String> generateAllPathsInList(){
		int maxLength=getMaxDepth();
		LinkedList<String> paths=new LinkedList<String>();
		Stack<NodeTraceElement> stack=new Stack<NodeTraceElement>();
		stack.add(new NodeTraceElement(adjList[startNodeIndex], "",0));
		while(!stack.isEmpty()){
			NodeTraceElement currentTrace=stack.pop();
			paths.add(currentTrace.getCurrentTrace());
			for(EdgeTransitionSystem transitions:currentTrace.getNode().getNeighbors()){
				if(currentTrace.getTraceLength()<=maxLength)
					stack.push(new NodeTraceElement(transitions.getToNode(), (currentTrace.getCurrentTrace().equals("")?currentTrace.getCurrentTrace():currentTrace.getCurrentTrace()+"-")+transitions.getTransitionName(), currentTrace.getTraceLength()+1));
				
			}
		}
		return paths;
	}
	
	/** Method for generating all the possible paths in the graph with the max length - the max depth of the graph
	 * @return hash table where every path for every node is stored in one place
	 */
	public NodePathsHashTable generateAllPaths(){
		NodePathsHashTable hashTable=new NodePathsHashTable();
		int maxLength=getMaxDepth();
		Stack<NodeTraceElement> stack=new Stack<NodeTraceElement>();
		stack.add(new NodeTraceElement(adjList[startNodeIndex], "",0));
		while(!stack.isEmpty()){
			NodeTraceElement currentTrace=stack.pop();
			if(!currentTrace.getCurrentTrace().equals(""))
				hashTable.insertNodePath(currentTrace.getNode().getIndex(), currentTrace.getCurrentTrace());
			for(EdgeTransitionSystem transitions:currentTrace.getNode().getNeighbors()){
				if(currentTrace.getTraceLength()<=maxLength)
					stack.push(new NodeTraceElement(transitions.getToNode(), (currentTrace.getCurrentTrace().equals("")?currentTrace.getCurrentTrace():currentTrace.getCurrentTrace()+" ")+transitions.getTransitionName(), currentTrace.getTraceLength()+1));
				
			}
		}
		return hashTable;
	}
	
	/** Method for getting all the nodes in the graph
	 * @return the list of all of the nodes in the graph
	 */
	public LinkedList<NodeTransitionSystem> getAllNodes(){
		LinkedList<NodeTransitionSystem> lista=new LinkedList<NodeTransitionSystem>();
		for(int i=0;i<=maxNodeIndex;i++)
			lista.addLast(adjList[i]);
		return lista;
	}
	
	/** Method for getting all the transitions in the graph
	 * @return the list of all transitions in the graph
	 */
	public LinkedList<EdgeTransitionSystem> getAllTransitionsList(){
		LinkedList<EdgeTransitionSystem> lista=new LinkedList<EdgeTransitionSystem>();
		for(int i=0;i<=maxNodeIndex;i++)
			if(adjList[i]!=null)
			for(EdgeTransitionSystem transition:adjList[i].getNeighbors())
				lista.addLast(transition);
		return lista;
	}
	
	/** Method for getting the name of the node for a given index
	 * @param index - the index of the node
	 * @return - the name of the node
	 */
	public String getNodeName(int index){
		return adjList[index].getName();
	}
}
